﻿#ifndef __COUNTING__
#define __COUNTING__
#include "SortTool.h"
#define MAX_NUM 99999
//计数排序，效率为线性的O(n)
//它假设待排序的项的数值范围在0~MAX_NUM之间
//它是稳定的

void counting(int arr[], int left, int right){
	if(right == left || arr == NULL) return;
	static int count[MAX_NUM],//统计数组，自动初始化为0（为了节约内存，可以申明为非static，然后手动初始化）
			   aux[MAX_ARRAY_NUM];
	assert(right > left && (right-left) < MAX_ARRAY_NUM);
	for(int i = left; i <= right; ++i) assert(arr[i] <= MAX_NUM && arr[i] >= 0);//非必须检查：待排序项是否符合排序算法的限制
	for(int i = left; i <= right; ++i)	++count[arr[i]];
	for(int i = 1; i < MAX_NUM; ++i) count[i] += count[i-1];
	for(int i = left; i <= right; ++i)	aux[--count[arr[i]]] = arr[i];//back 从0位开始存储，而count 的最小值为1故--放在前面
	for(int i = left; i <= right; ++i) arr[i] = aux[i];
}
#endif